후위 표기법에서 전위 표기법으로 변환

목표

당신의 목표는 후위 표현식 (역폴란드 표기법)을 그에 해당하는 전위 표현식 (폴란드 표기법)으로 변환하는 것입니다. 이를 위해 표현식 트리를 구축하고 탐색합니다.

알고리즘

1. 표현식 트리 생성하기: 스택을 사용하여 후위 표현식을 왼쪽에서 오른쪽으로 처리합니다.
   • 만약 피연산자 (예: A, B)를 찾으면 해당 피연산자를 루트로 하는 단일 노드 트리를 만들고 스택에 넣습니다.
   • 만약 연산자 (예: +, *)를 찾으면 스택에서 두 개의 트리를 꺼냅니다. 먼저 꺼낸 것은 오른쪽 자식 (T₂)이고, 두 번째로 꺼낸 것은 왼쪽 자식 (T₁)입니다. 연산자를 루트로 하는 새로운 트리를 만들어 스택에 다시 넣습니다.
2. 전위 문자열 생성하기: 모든 토큰을 처리한 후 스택에는 완전한 표현식 트리가 남아 있습니다. 이 트리에 대해 전위 순회 (루트 → 왼쪽 → 오른쪽)를 수행하여 최종 전위 표현식을 생성합니다.

예시

후위 표현식 A B + C *에 대해 알고리즘은 다음 트리를 구성합니다:

  *
   / \
  +   C
 / \
A   B

전위 순회 결과 전위 표현식은: * + A B C.

입출력 형식

입력

• 줄 1: 정수 N (1 ≤ N ≤ 1000), 토큰의 개수입니다.
• 줄 2: 후위 표현식, 토큰은 N개의 토큰이 공백으로 분리되어 있습니다.

토큰 규칙

• 피연산자: 대문자 한 글자 (A-Z).
• 연산자: 네 가지 이항 연산자: +, -, *, /.

출력

• 공백으로 분리된 토큰들로 이루어진 해당 전위 표현식을 포함한 단일 줄입니다.

예제

예제 1:

5

A B + C *

* + A B C

예제 2:

7

A B C * + D /

/ + A * B C D

예제 3:

7

A B + C D - *

* + A B - C D

제한 사항